package com.zwj.interview.二分查找;

/**
 * 在一个长度大于或等于3的数组中，任意相邻的两个数字都不相等。该数组的前若干数字是递增的，
 * 之后的数字是递减的，因此它的值看起来像一座山峰。请找出山峰顶部，即数组中最大值的位置。
 * 例如，在数组[1，3，5，4，2]中，最大值是5，输出它在数组中的下标2
 *
 * 寻找山峰
 */
public class 寻找数组中的最大值 {

    public int peakIndexInMountainArray(int[] nums) {
        //在一个长度为n的山峰数组中，由于第1个数字和最后一个数字都不可能是最大值，因此初始查找范围为数组下标从1到n-2的部分
        int left = 1;
        int right = nums.length - 2;
        while (left <= right) {
            int mid = (left + right) / 2;
            //如果这个数字大于它前后两个数字，那么它就是最大值
            if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }
            //如果它大于它前面的数字，那么它位于数组递增的部分,接下来查找它的后半部分；
            if (nums[mid] > nums[mid - 1]) {
                left = mid + 1;
            } else {
                //否则它位于数组递减的部分，接下来查找它的前半部分
                right = mid - 1;
            }
        }
        return -1;
    }

}
